class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        vector<vector<bool> > dp(n,vector<bool>(n,false));
        for(int i = 0;i < n;i++){
            if(s[i] == '*'){
                dp[i][i] = true;
            }
        }
        for(int i = n-1;i >= 0;i--){
            for(int j = i+1;j < n;j++){
                if(j - i <= 1){
                    if((s[i]=='('||s[i]=='*') && (s[j]==')'||s[j]=='*')){
                        dp[i][j] = true;
                    }
                }
                else if((s[i]=='('||s[i]=='*') && (s[j]==')'||s[j]=='*')){
                    dp[i][j] = dp[i+1][j-1];
                    for(int k = i;k < j && !dp[i][j];k++){
                        dp[i][j] = dp[i][k] && dp[k+1][j];
                    }
                }  
            }
        }
      
        return dp[0][n-1];
    }
};
